package leetcode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0494.java
 * @Author : WangRuoyu
 * @Date 2023/11/6 21:22
 */


public class Q0494 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += Math.abs(nums[i]);
        }
        if (target > sum || target < -sum) return 0;
        int[][] f = new int[nums.length + 1][2 * sum + 1];
        f[0][sum] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= 2 * sum; j++) {
                if (j >= nums[i - 1] && j <= 2 * sum + nums[i - 1]) f[i][j] += f[i - 1][j - nums[i - 1]];
                if (j >= -nums[i - 1] && j <= 2 * sum - nums[i - 1]) f[i][j] += f[i - 1][j + nums[i - 1]];
            }
        }
        return f[nums.length][target + sum];
    }

    public static void main(String[] args) {
        Q0494 sl = new Q0494();
        int[] nums = {1};
        int target = 2;
        System.out.println(sl.findTargetSumWays(nums, target));
    }
}